 #define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int trap(vector<int>& height) {
        int ret = 0;
        int len = height.size();
        //特殊情况,说明此时中间并不能接到任何的雨水
        if (len < 3)  return 0;

        //求从左往右对应高度的最大值，还有求从右到左的高度最大值
        vector<int> leftMax(len);
        leftMax[0] = height[0];
        for (int i = 1; i < len; i++)
            leftMax[i] = max(leftMax[i - 1], height[i]);

        vector<int> rightMax(len);
        rightMax[len - 1] = height[len - 1];
        for (int i = len - 2; i >= 0; i--)
            rightMax[i] = max(rightMax[i + 1], height[i]);

        for (int i = 0; i < len; i++)
            ret += min(leftMax[i], rightMax[i]) - height[i];

        return ret;
    }
};